The problem of tracking moving objects has been studied for a long time. Typically, methods for detecting object states such as position and orientation in single frames, e.g. using edge information, templates or machine learning, are combined with dynamic models in order to gain robustness.
There are numerous techniques for object detection in individual frames. Depending on the situation different techniques can be used, such as blob detection, edge detection, dynamic shape matching, template matching or feature points. Recently methods based on machine learning have become popular.
When it comes to tracking of objects in image sequences, there are several interesting techniques that are appropriate in different settings. Examples of such techniques are Kalman filtering, as described in Koller, D., Daniilidis, K. and Nagel, H.-H., “Model-Based Object Tracking in Monocular Image Sequences of Road Traffic Scenes”, International Journal of Computer Vision, vol. 10, pages 257-281, 1993, particle filtering, as described in Isard, M. and Blake, A., “A Visual Tracking by Stochastic Propagation of Conditional Density”, Proc. 4th European Conf. Computer Vision, 1996, continuous state space methods, hidden Markov models (HMM) as described in Movellan, J., Hershey, J. and Susskind, J., “Real-Time Video Tracking using Convolution HMMs”, Computer Vision and Pattern Recognition, 2004, and multi hypothesis tracking as described in Reid, D., “An Algorithm for Tracking Multiple Targets”, IEEE Transaction on Automatic Control, vol. 24(6), pages 843-854, 1979.
When several objects are considered one model for each tracked object is often used. However, the data association problem of deciding which detections should be used to update which models has to be solved. One classical solution, joint probabilistic data association filter (JPDAF), is presented in Bar-Shalom, Y., Fortmann, T. E. and Scheffe, M., “Joint Probabilistic Data Association for Multiple Targets in Clutter”, Proc. Conf. on Information Sciences and Systems, 1980. A different approach is to only track the objects when they are well separated and then later try to label the tracks, and give corresponding tracks the same label. A real time version of this using Bayesian networks can be found in Jorge, P. M., Abrantes, A. J. and Marques, J. S., “On-line Tracking Groups of Pedestrians with Bayesian Networks”, European Conference on Computer Vision, 2004.
These systems can be made robust by using multi hypothesis tracking. In Streit, R. L. and Luginbuhl, T. E., “Probabilistic Multi-Hypothesis Tracking”, Technical Report 10428, Naval Undersea Warfare Center, Newport, 1995, a probabilistic multi-hypothesis tracker (PMHT) is proposed where the data association problem does not have to be solved explicitly in every frame. Instead the probability of each measurement belonging to each model is estimated, but the problems of object entering and exiting the model must still be solved separately. In Davey, S. J., Gray, D. A. and Colegrove, S. B., “A Markov Model for Initiating Tracks with the Probabilistic Multi-Hypothesis Tracker”, Proc. 5th International Conference on Information Fusion, pages 735-742, 2002, the PMHT is extended with the notion of track visibility to solve the problem of track initiation. However, their system is still based on the creation of candidate tracks that may not be promoted to real tracks but still influence other real tracks.
In Hue, C., Le Cadre, J. P. and Perez, P., “Tracking Multiple Objects with Particle Filtering”, IEEE Transactions on Aerospace and Electronic Systems, vol. 38, pages 791-812, 2002, the state space of a particle filter is extended to handle multiple objects, but a fixed number of objects is assumed, which means that only the data association problem is handled and not the entry and exit problems. In Isard, M. and MacCormick, J., “BraMBLe: A Bayesian Multiple-Blob Tracker”, International Conference on Computer Vision, pages 34-41, 2001, a particle filter in which the number of objects being tracked may vary during tracking is presented. The state space is parameterised using one discrete parameter, the number of visible objects, and a varying number of continuous parameters specifying the state of each object. However, the particle filtering is used, which is an approximative method.
In Xie, X. and Evans, R., “Multiple Target Tracking and Multiple Frequency Line Tracking Using Hidden Markov Models”, IEEE Transactions on Signal Processing, vol. 39, pages 2659-2676, 1991, a method for one dimensional tracking of several received radio signals within a spectrum is presented. This means that several objects can be tracked and their entry and exit can be determined. However, when a large amount of objects and a large amount of possible positions are to be handled, the state space becomes too big to be solved by the standard Viterbi algorithm.